package me.eg.sixth;

import javafx.util.Pair;

/**
 * 673. 最长递增子序列的个数
 * <p>
 * 给定一个未排序的整数数组，找到最长递增子序列的个数。
 * <p>
 * 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
 * <p>
 * 链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
 */
public class FindNumberOfLIS {
    /**
     * 解法：动态规划
     * 时间复杂度：O(N * N)
     * 空间复杂度：O(N)
     * @param nums
     * @return
     */
    public int findNumberOfLIS(int[] nums) {
        Pair<Integer, Integer>[] lenOfLIS = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int maxLenOfLIS = 0;
            int cntOfMaxLen = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (lenOfLIS[j].getKey() > maxLenOfLIS) {
                        maxLenOfLIS = lenOfLIS[j].getKey();
                        cntOfMaxLen = lenOfLIS[j].getValue();
                    } else if (lenOfLIS[j].getKey() == maxLenOfLIS) {
                        cntOfMaxLen += lenOfLIS[j].getValue();
                    }
                }
            }
            lenOfLIS[i] = new Pair<>(maxLenOfLIS + 1, cntOfMaxLen == 0 ? 1 : cntOfMaxLen);
        }

        int maxLen = 0;
        int cnt = 0;
        for (int i = 0; i < lenOfLIS.length; i++) {
            if (lenOfLIS[i].getKey() > maxLen) {
                maxLen = lenOfLIS[i].getKey();
                cnt = lenOfLIS[i].getValue();
            } else if (lenOfLIS[i].getKey() == maxLen) {
                cnt += lenOfLIS[i].getValue();
            }
        }
        return cnt;
    }
}
